package arithmetic.LeetCode;

import org.junit.jupiter.api.Test;

/**
 * 844. 比较含退格的字符串
 * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
 * 注意：如果对空文本输入退格字符，文本继续为空。
 *
 * 
 * 示例 1：
 * 输入：s = "ab#c", t = "ad#c"
 * 输出：true
 * 解释：s 和 t 都会变成 "ac"。
 *
 * 示例 2：
 * 输入：s = "ab##", t = "c#d#"
 * 输出：true
 * 解释：s 和 t 都会变成 ""。
 *
 * 示例 3：
 * 输入：s = "a#c", t = "b"
 * 输出：false
 * 解释：s 会变成 "c"，但 t 仍然是 "b"。
 * 
 *
 * 提示：
 * 1 <= s.length, t.length <= 200
 * s 和 t 只含有小写字母以及字符 '#'
 * 
 *
 * 进阶：
 * 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
 *
 *
 * 链接：https://leetcode.cn/problems/backspace-string-compare
 * @author jiangfeng on 2022/6/11
 */
public class DeleteEquels {
    @Test
    public void test(){
        //System.out.println(backspaceCompare( "ab##","c#d#"));
        //System.out.println(backspaceCompare( "xywrrmp",  "xywrrmu#p"));

        //System.out.println(backspaceCompare2( "xywrrmp",  "xywrrmu#p")); // 通过

        //System.out.println(backspaceCompare2(   "ab##" ,"c#d#")); // 通过 true
        //System.out.println(backspaceCompare2(   "bxj##tw","bxo#j##tw")); // true
        // "bxj##tw" ,"bxj###tw"
        //System.out.println(backspaceCompare2(   "bxj##tw" ,"bxj###tw"));  //false

        System.out.println(backspaceCompare2( "ab##","c#d#")); //true
        //
        System.out.println(backspaceCompare2( "isfcow#","isfcog#w#")); //true

    }

    // 此解法有问题,太多逻辑搞不清,太多特殊情况特别绕
    public boolean backspaceCompare(String s, String t) {
        int x = 0;
        int y = 0;
        while (x < s.length() || y < t.length()) {
            while(x < s.length() && s.charAt(x)=='#'){
                x++;
            }

            while(y < t.length() && t.charAt(y)=='#' ){
                y++;
            }

            if(x == s.length() && y == t.length()){
                return true;
            }
            if (x == s.length() ||  y == t.length()){
                return false;
            }
            if (s.charAt(x) == t.charAt(y)) {
                x++;
                y++;
            } else {
                // 出现一个不一样, 看有没有可以推格子符可以删除, 没有就返回false;
                boolean xBlank = isBlank(s,x);
                boolean yBlank = isBlank(t, y);
                if( xBlank && yBlank ){
                    x++;
                    y++;
                }else{
                    //到了最后的时候
                    if(x == s.length()-1 && yBlank){


                        continue;
                    }
                    return false;
                }
            }
        }
        if (x < s.length() || y < t.length()) {
            return false;
        }
        return true;
    }

    public boolean isBlank(String s, int offset) {
        // 有多少字符数
        int charSize = 1;
        // 有多少退格数
        int backSize = 0;
        int index = offset+1;
        while(index<s.length()) {
            if(s.charAt(index)=='#'){
                backSize++;
                if(backSize>=charSize){
                    return true;
                }
            }else{
                charSize++;
            }
            index++;
        }
        return false;
    }

    public boolean backspaceCompare2(String s, String t) {
        int j = s.length()-1,k = t.length()-1;
        while(j>=0 || k>=0){
            int count = 0;
            // xo#j##
            j = cal(j,s);
            k = cal(k,t);
            if(j>=0 && k>=0){
                if(s.charAt(j)==t.charAt(k)){
                    j--;
                    k--;
                    continue;
                }else{
                    return false;
                }
            }

            if (j >= 0) {
                j = cal(j, s);
            }
            if (k >= 0) {
                k = cal(k, t);
            }
            if (j >= 0 || k >= 0) {
                return false;
            }
        }
        if(j < 0 && k < 0){
            return true;
        }
        return false;

    }

    private int cal(int j,String s){
        int count = 0;
        while(j>=0 && (s.charAt(j) == '#' || count >= 0)){
            if(count == 0 && s.charAt(j) != '#' ){
                return j;
            }
            if(s.charAt(j) == '#'){
                count++;
            }else{
                count--;
            }
            j--;
        };
        /*// 第二次 防止遇到 退格过程中有有#号
        while (count >= 0) {
            if (j>=0 && s.charAt(j) == '#') {
                count++;
            } else {
                count--;
                if(count<0){
                    return j;
                }
            }
            j--;
        }*/
        return j;
    }


    @Test
    public void test3(){
        System.out.println(backspaceCompare3(   "ab##" ,"c#d#")); // 通过 true
        System.out.println(backspaceCompare3(   "bxj##tw","bxo#j##tw")); // true
        System.out.println(backspaceCompare3(   "bxj##tw" ,"bxj###tw"));  //false

        System.out.println(backspaceCompare3( "ab##","c#d#")); //true
        //
        System.out.println(backspaceCompare3( "isfcow#","isfcog#w#"));
    }
    public boolean backspaceCompare3(String s, String t) {
        int j = s.length()-1,k = t.length() -1,skipS = 0,SkipT = 0;
        while(j>=0 || j >=0){
            while(j>=0){
                if(s.charAt(j)=='#'){
                    skipS++;
                    j--;
                }else if(skipS>0){
                    skipS--;
                    j--;
                }else{
                    break;
                }
            }

            while(k>=0){
                if(t.charAt(k)=='#'){
                    SkipT++;
                    k--;
                }else if(SkipT>0){
                    SkipT--;
                    k--;
                }else{
                    break;
                }
            }

            if(j>=0 && k>=0 ){
                if(s.charAt(j)==t.charAt(k)){
                    j--;
                    k--;
                    continue;
                }else{
                    return false;
                }
            }
            if(j>=0 || k>=0 ){
                return false;
            }

        }
        return true;
    }
}
